// 给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。

// 添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。

// 将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。

// 如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

// 示例 1:

// 输入: 
// 二叉树如下所示:
//        4
//      /   \
//     2     6
//    / \   / 
//   3   1 5   

// v = 1

// d = 2

// 输出: 
//        4
//       / \
//      1   1
//     /     \
//    2       6
//   / \     / 
//  3   1   5   

// 示例 2:

// 输入: 
// 二叉树如下所示:
//       4
//      /   
//     2    
//    / \   
//   3   1    

// v = 1

// d = 3

// 输出: 
//       4
//      /   
//     2
//    / \    
//   1   1
//  /     \  
// 3       1
// 注意:

// 输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
// 输入的二叉树至少有一个节点。

#include "../stdc++.h"

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) {
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        }
        int level{0};
        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            ++level;
            int n = q.size();
            if (level == d - 1) {
                while (n--) {
                    TreeNode* node = q.front();
                    q.pop();
                    TreeNode* newLeft = new TreeNode(v);
                    TreeNode* newRight = new TreeNode(v);
                    if (node->left) newLeft->left = node->left;
                    if (node->right) newRight->right = node->right;
                    node->left = newLeft;
                    node->right = newRight;
                }
                break;
            }
            while (n--) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return root;
    }
};

// 深度优先搜索
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (nullptr == root) {
            return nullptr;
        }
        if (1 == depth) {  
            return new TreeNode(val, root, nullptr);
        }
        if (2 == depth) {
            root->left = new TreeNode(val, root->left, nullptr);
            root->right = new TreeNode(val, nullptr, root->right);
        } else {
            root->left = addOneRow(root->left, val, depth - 1);
            root->right = addOneRow(root->right, val, depth - 1);
        }
        return root;
    }
};
